package com.midea.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class LeetCode39 {
    public static void main(String[] args) {
        int[] a = {2,3,6,7};
        System.out.println(combinationSum(a,7));
    }
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(candidates,target,0,list,result);
        return result;
    }



    static void dfs(int[] nums,int target,int count,List<Integer> list,List<List<Integer>> result){
        if (count >= target){
            if (count == target){
                List<Integer> temp = new ArrayList<>();
                temp.addAll(list);
                Collections.sort(temp);
                if (!result.contains(temp)){
                    result.add(temp);
                }
            }
            return;
        }
        for (int i = 0;i<nums.length;i++){
            list.add(nums[i]);
            count = count + nums[i];
            dfs(nums,target,count,list,result);
            list.remove(list.size()-1);
            count = count - nums[i];
        }
    }
}
